package Problem3;

import java.util.ArrayList;

public class Main {

	public static void main(String[] args) {
		ArrayList<Integer> primeNumbers = findPrimes();
		int answer = 0;
		for (int i = primeNumbers.size() - 1; i > 0; i--) {
			int compare = primeNumbers.get(i);
			if (600851475143. % compare == 0) {
				answer = primeNumbers.get(i);
				break;
			}
				
		}
		System.out.println(answer);
	}
	public static ArrayList<Integer> findPrimes(){
		ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
		
		primeNumbers.add(2);
		// 775,146 is the square root of 600851475143.  No primes matter after that number.
		for (int i = 2; i <= 775146; i++) {
			boolean found = true;
			for (int prime: primeNumbers) {
				if ((i % prime) == 0){
					found = false;
					break;
				}
			}
			if (found)
				primeNumbers.add(i);
		}
		
		return primeNumbers;
	} 
}
